package 算法;

import java.util.Arrays;

/**
 * @author coderFu
 * @create 2022/3/18
 */
public class CoderTest {

    public static void main(String[] args) {

        int[] sort = new CoderTest().sort(new int[]{1, 5, 7, 2});
        System.out.println(Arrays.toString(sort));
    }

    public int[] sort( int[] nums) {
        // 归并排序

        int[] array = new int[nums.length];
        sort2(nums,0,nums.length-1,array);
        return nums;
    }

    public void sort2(int[] nums, int left, int right, int[] temp){

        if(left < right){
            int mid = left +(right-left)/2;
            sort2(nums,left,mid,temp);
            sort2(nums,mid+1,right,temp);
            merge(nums,left,mid,right,temp);
        }
    }
    public void merge(int[] nums,int left, int mid, int right, int[] temp){
        int i=left;
        int j=mid+1;
        int t=0;
        while(i<=mid && j<=right){
            if(nums[i] < nums[j]){
                temp[t++] = nums[i++];
            }else{
                temp[t++] = nums[j++];
            }
        }

        while(i<=mid){
            temp[t++] = nums[i++];
        }
        while(j<=right){
            temp[t++] = nums[j++];
        }
        t=0;
        while(left<=right){
            nums[left++] = temp[t++];
        }
    }



}
